package 力扣;

/**
 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 输出：6
 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 示例 2：

 输入：height = [4,2,0,3,2,5]
 输出：9
 */

public class _42接雨水 {

    public int trap(int[] height) {
        if( height == null || height.length == 0) return 0;
        int max = 0;
        int len = height.length;
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];
        maxLeft[0] = height[0];
        // 所有遍历左边界和右边界都需要忽略
        for (int i = 1; i < len; i++) { //从左往右找最大的值
            maxLeft[i] = Math.max(height[i],maxLeft[i-1]);
        }
        maxRight[ len-1 ] = height[ len -1];
        for (int i = len-2; i >=0 ; i--) { // 从右往走找最大的值
            maxRight[i] = Math.max(height[i],maxRight[i+1]);
        }

        for (int i = 1; i < len-1; i++) {
            max += Math.min(maxLeft[i],maxRight[i])  - height[i];
        }
        return max;
    }
}
